package com.xjj.recursion;

import java.util.ArrayList;
import java.util.List;

public class M0077Combinations {

    private final List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        getSub(1, n, k, new ArrayList<>());
        return result;
    }

    private void getSub(int index, int max, int capacity, List<Integer> tmp) {
        // System.out.println(tmp);

        // 注意顺序,一开始进来tmp加过后的状态是没判断,没加入结果的
        if (tmp.size() == capacity) {
            result.add(new ArrayList<>(tmp));
            // System.out.println("r1" + tmp);
            return;
        }
        if (index > max || (max - index + 1 + tmp.size()) < capacity) {
            // System.out.println("r1" + tmp);
            return;
        }

        // 不加上此时index的值
        getSub(index + 1, max, capacity, tmp);

        // 加上此时index的值
        tmp.add(index);
        getSub(index + 1, max, capacity, tmp);
        // tmp还原此时未加的状态
        tmp.remove(tmp.size() - 1);
    }
}
